Scanners for electronically forming an image of an original are known. Typically, the captured image provided by a scanner is a pixel data array that is stored in memory in a digital format. A distortion-free image requires a faithful mapping of the original image to the pixel data array. Scanners typically use mechanical constraint during the image capture process in order to maximize the likelihood of faithful mapping. Types of scanners known in the art include drum scanners, flatbed scanners, two-dimensional array scanners, sheet-fed scanners and hand scanners. The present invention is particularly applicable to hand scanners.
Conventional hand scanners require a user to move a linear array of electrooptical sensor elements over an original. The movement is generally by hand manipulation, but in some embodiments is motor driven. Array-position information is determined using methods such as those employed in operation of a computer "mouse." As a linear sensor array is moved, the rotation of wheels, balls or rollers that are in contact with the original is sensed, and the position information is determined from the mechanical details of the rotation. In general, the surface of the mechanical element in contact with the original has a high coefficient of friction, e.g. rubber, so as to resist slip and skid. A cylindrical roller or two wheels connected by a rigid axle may be used to enforce a single translational degree of freedom during the scanning process. A straight-edge or other fixture is often used to fix the scan direction with respect to the original and to further enforce the translational constraint provided by the pair of wheels or the roller. Nevertheless, the position encoder approach is one that is often susceptible to slips and skips, so that the pixel data array loses its correspondence with the image on the original.
Hand scanners are typically connected directly to a separate computer for image data storage, processing, and use. The scanners provide feedback to the user, typically by means of green or red light emitting diodes, to maintain the appropriate speed for the desired image resolution. Some hand scanners use electromagnetic brakes to prevent the user from dragging the scanner over the image too rapidly, with the mechanical resistance increasing with increases in scanning speed.
Hand scanners utilize relatively small imaging arrays and generally cannot handle larger than A6 documents in a single pass. This requires stitching algorithms to join together multiple swaths of a larger document. Swath stitching may be done in a separate operation by a separate computer. Scanning a multi-page business document or report with a hand scanner is a tedious process that often yields low-quality results. Techniques for stitching image swaths are known in the scanning art. These techniques typically require a pair of complete image swaths and produce a single, global transformation which brings the two swaths into registration. Improved techniques are taught in the International Patent Application Publication No. WO 96/27257.
As previously noted, some type of fixture is typically used with a hand scanner. In the absence of a fixture, there is a tendency to impose some rotation as the hand scanner is moved across an original. If the user's elbow is resting on a flat surface during movement of the scanner, the rotation is likely to have a radius defined by the distance between the scanner and the user's elbow. As a consequence, the scanned electronic image will be distorted. Other curvilinear movements during a swath of the scanner will also create distortions.
In forming a scanned electronic image it is necessary to acquire navigation information that is acquired along with image data. A hand scanner in which navigation information is obtained without compromise to ease of use of the scanner is described in U.S. Pat. No. 5,578,813. The navigation information is acquired by means of at least one navigation sensor that detects inherent structure-related properties of an original being scanned. Movement of an image sensor along the original is tracked by monitoring variations of the inherent structure-related properties as the image sensor is moved relative to the original. The inherent structure-related properties that are monitored are inherent structural features, such as paper fibers, or other constituents of the original. Navigation can alternatively be speckle-based, wherein movement of the image sensor along the original is tracked by monitoring variations of speckle patterns produced using coherent illumination for acquiring the navigation information. Movement of the scanner across the surface of the image to be scanned can thus be essentially arbitrary, as it is not constrained.
"Inherent structure-related properties" are properties of the original that are attributable to factors that are independent of forming image data and/or of systematic registration data on the original. The navigation information may be formed by generating a position signal that is responsive to detection of inherent structure-related properties, such as a position signal of speckle information or a position signal that permits tracking of individual inherent structural features. "Inherent structural features" are those features of an original that are characteristic of processes of forming the original and are independent of forming image data and/or systematic registration data on the original. For example, if the original recorded media is a paper product, the inherent structural features of interest may be paper fibers. As another example, navigation of the image sensor across a glossy original or an overhead transparency film may be determined by tracking surface texture variations that affect specular fields. Typically, the inherent structural features are microscopic, e.g. between 10 and 40 .mu.m, features of surface texture.
The present invention is directly applicable to hand scanners as taught in International Patent Application Publication No. WO 96/27257 and U.S. Pat. No. 5,578,813, both of which applications are incorporated herein by reference to the extent that this is permissible by national law.
Processing problems are caused by the unconstrained nature of input in many of the embodiments set out in the above prior art documents. In order to be sure that the pixel array for the reconstructed image will be capable of representing all the data captured, it is necessary for it to be relatively large. As data capture could begin at any point on the image, in conventional structures it would be necessary to use a pixel grid several times larger than the image to be captured. It is necessary with such an approach to allocate considerable memory to storage of pixel array data, thus significantly increasing expense.
The present invention aims to provide a method that significantly reduces the memory requirements for storing an image captured in such an unconstrained manner. In particular aspects, the invention provides for reduction of the computational cost and increases the speed of forming a reconstructed image from an arbitrarily obtained captured image. The method is particularly directed to freehand scanning, and freehand scanning devices.